% !TEX encoding = UTF-8 Unicode
\chapter{$P$-círculos y el diagrama de Voronoi del punto más lejano}\label{Diagrama Voronoi}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\fancyhead[LO]{\bfseries\rightmark}
\fancyhead[RE]{\bfseries\leftmark}

\section{Nuestro problema}

Sea $P$ un conjunto de $n$ casas representadas por $n$ puntos en el plano.
Nuestro objetivo es ofrecer cobertura radiofónica a cada casa utilizando una antena inalámbrica.
La potencia de transmisión de la antena define un radio de cobertura $r$ alrededor del punto de emisión, tal que toda casa que tenga cobertura se encuentra a distancia a lo más $r$ de la antena.
Es claro que si aumentamos la potencia de nuestra antena, aumentará su consumo de energía y por ende también su costo de operación.
Buscaremos siempre ofrecer el servicio de la manera más barata, por lo que
nuestro objetivo es encontrar la posición y potencia óptimas para la antena, de manera que todas las casas se encuentren dentro de su radio de cobertura, ver Figura~\ref{fig:ProblemaCoberturaRadiofonica}.

En este trabajo, un círculo es el conjunto de puntos a distancia a lo más $r$ de un punto en el plano, $r\geq 0$.
Claramente nuestra antena, junto con su radio de cobertura, definen un círculo en el plano.
El problema de cobertura óptima se traduce entonces en encontrar el círculo de radio mínimo que contenga los $n$ puntos de $P$.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.6\textwidth]{img/cap1/NuestroProblema.pdf}
\caption{\small La antena inalámbrica de transmisión radiofónica dando cobertura a un conjunto de casas representadas por este conjunto de puntos.}
\label{fig:ProblemaCoberturaRadiofonica}
\end{center}
\end{figure}

\pagebreak
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{El diagrama de Voronoi del punto más \\ lejano}
Sea $P$ un conjunto de $n$ puntos en el plano y sea $C$ un círculo. Diremos que $C$ es un $P$-círculo si contiene a todos los puntos de $P$.

Sea $C_P$ el $P$-círculo de radio mínimo y sea $c_P$ su centro. Es fácil ver que la circunferencia de $C_P$ debe pasar por al menos un punto de $P$, de lo contrario siempre podríamos reducir el radio del círculo de manera que todos los puntos de $P$ sigan en el interior.
Sea $p$ un punto de $P$ sobre la frontera del círculo $C_P$. Note que
la distancia de $c_P$ a cualquier otro punto de $P$ es a lo más $d(c_P, p)$, dónde $d(*,*)$ denota la distancia euclidiana entre dos objetos geométricos en el plano.
Visto de otra forma, $p$ es uno de los puntos más lejanos de $c_P$
de entre los elementos del conjunto $P$; ver Figura~\ref{fig:EnclosingCircle-Voronoi}(a).
Este concepto de lejanía nos lleva a pensar en las siguientes preguntas. 
?`Cuáles serán los puntos en el plano para los que $p$ es el elemento más lejano dentro del conjunto $P$? 
?`Se podrá dar una caracterización de este conjunto de puntos?
El diagrama de Voronoi del punto más lejano de $P$ es el objeto geométrico que da respuesta a estas y otras preguntas.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=1\textwidth]{img/cap1/EnclosingCircle-Voronoi.pdf}
\caption{\small $a)$ El círculo $C_P$ y su centro $c_P$.
$b)$ El diagrama de Voronoi del punto más lejano de $\{p_0, \ldots, p_6\}$.}
\label{fig:EnclosingCircle-Voronoi}
\end{center}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{¿Qué es el Diagrama de Voronoi del punto más lejano?}
Sea $P = \{p_1, \ldots, p_n\}$ un conjunto de $n$ puntos en el plano.
El diagrama de Voronoi del punto más lejano de $P$ o simplemente diagrama de Voronoi de $P$~\footnote{Cabe resaltar que nombre corto de \emph{diagrama de Voronoi} es comúnmente usado en la literatura para referirse al diagrama de Voronoi del punto más cercano, sin embargo en este trabajo sólo utilizaremos el diagrama del punto más lejano por lo que no habrá confusiones.}, 
es una división del plano en $n$ regiones $R(p_1), \ldots, R(p_n)$, una por cada punto de $P$, con la propiedad de que
un punto $x$ yace en la región $R(p_i)$ si y sólo si $d(p_i,x) \geq d(p_j,x)$, $1\leq i, j\leq n$.

Si suponemos que $P$ consta únicamente de dos puntos $p,q$, entonces la bisectriz de $p$ y $q$ divide el plano en dos semiplanos cerrados que definen las regiones de Voronoi $R(p)$ y $R(q)$; ver Figura~\ref{F_ SemiplanoR(p)}.

\begin{figure}[htbp]
\begin{center}
\includegraphics{img/cap1/SemiplanoR(p).pdf}
\caption{\small El diagrama de Voronoi de un conjunto de dos puntos.}
\label{F_ SemiplanoR(p)}
\end{center}
\end{figure}

Sea $\Pi_j$ el semiplano cerrado inducido por la bisectriz de $p_i$ y $p_j$ que contiene a $p_j$.
Otra forma de definir a $R(p_i)$ es la siguiente:

\begin{defi}\label{Definicion Region Voronoi}
Sea $p_i$ un punto en $P$,
$$R(p_i) = \bigcap_{j\neq i} \Pi_j.$$
\end{defi}


Es fácil verificar que ambas definiciones de $R(p_i)$ son equivalentes. 
Note que si $x\in \Pi_j$, entonces $x$ está más lejos de $p_i$ que de $p_j$. 
Como $x$ pertenece a cada $\Pi_j$ para todo $j\neq i$, 
entonces $x$ está más lejos de $p_i$ que de cualquier otro punto de $P$.


De la definición anterior podemos deducir varias cosas, 
en primer lugar observemos que la intersección que define a $R(p_i)$ puede ser vacía. 
Note también que $R(p_i)$ es una región convexa, 
ya que se define como la intersección finita de conjuntos convexos. 
Otra propiedad que se deriva, es que toda arista en la frontera de $R(p_i)$ 
está definida a partir de la bisectriz de dos puntos de $P$. 

Formalmente definimos al diagrama de Voronoi del punto más lejano de $P$, denotado por $V_P$ como sigue:
$$V_P = \{R(p) : p\in P\}.$$
Un ejemplo del diagrama $V_P$ se puede observar en la Figura~\ref{fig:EnclosingCircle-Voronoi}(b). Veremos a continuación varias propiedades del diagrama de Voronoi.

\begin{prop}\label{PuntoMasLejanoEnFrontera}
Para cualquier punto $x\in \mathbb{R}^2$, el punto de $P$ más lejano de $x$ yace sobre la frontera del cierre convexo de $P$.
\end{prop}
\begin{proof}

Un resultado bien conocido dice que un punto está en la frontera de un conjunto convexo, 
si y sólo si existe una recta soporte que pasa por ese punto. 
Donde una recta soporte se define como una línea recta que intersecta al conjunto, 
pero que lo deja completamente contenido en uno de los dos semiplanos cerrados que induce.

Sea $p$ uno de los puntos de $P$ más lejanos de $x$, y sea $C_x$ el círculo con centro en $x$ y radio $d(x,p)$.
Es claro que $C_x$ es un $P$-círculo, por consiguiente la tangente a $C_x$ por el punto $p$ es una recta soporte del cierre convexo de $P$, el resultado se sigue; ver Figura~\ref{fig:PuntoMasLejanoEnFrontera}.
\end{proof}

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.85\textwidth]{img/cap1/PuntoMasLejanoEnFrontera.pdf}
\caption{\small La prueba de la Proposición~\ref{PuntoMasLejanoEnFrontera}.}
\label{fig:PuntoMasLejanoEnFrontera}
\end{center}
\end{figure}

De la observación anterior podemos concluir que la región de Voronoi de un punto $p\in P$ es no vacía, 
si y sólo si $p$ forma parte de la frontera del cierre convexo de $P$. 
Por ende, podemos olvidarnos de los puntos interiores y suponer 
sin pérdida de generalidad que $P$ es un conjunto de puntos en posición convexa.

\begin{obs}\label{Circulo implica x in R(p)}
Sea $p$ en $P$ y sea $x$ un punto en el plano. Si el círculo con centro en $x$ y radio $d(x,p)$ es un $P$-círculo, entonces el punto $x$ pertenece a $R(p)$.
\end{obs}
La observación anterior se sigue directamente de la definición y con ella podemos deducir lo siguiente:

\begin{prop}\label{R(p) no acotada}
Si $p$ es un punto  en la frontera del cierre convexo de $P$, entonces la región de Voronoi $R(p)$ es un polígono convexo no acotado.
\end{prop}
\begin{proof}
Sea $x$ un punto en la frontera de $R(p)$, y sea $\ell_{x,p}$ la línea recta que pasa por $x$ y $p$. 
Consideremos la semirecta $\lambda $ contenida en $\ell_{x,p}$ con ápice $x$ y que no contiene a $p$.
Como $x\in R(p)$, entonces el círculo $C_x$ con centro en $x$ y radio $d(x,p)$ es un $P$-círculo.
Sea $y$ un punto en $\lambda $, y sea $C_y$ el círculo con centro en $y$ y radio $d(y,p)$. 
Es claro que $C_y$ es un $P$-círculo pues contiene a $C_x$.
Usando la Observación \ref{Circulo implica x in R(p)} tenemos que $y\in R(p)$ y por lo tanto $R(p)$ es un conjunto convexo no acotado. 
\end{proof}

Al ser $R(p)$ un polígono convexo no acotado, podemos concluir que su frontera contiene exactamente dos semirrectas, nos referimos a estas semirrectas como las aristas no acotadas de $R(p)$.

Note que cada región de Voronoi es un polígono definido por un conjunto de vértices y aristas.
Por ende nos interesará pensar en el diagrama de Voronoi como una gráfica, sin embargo hay que tener cuidado ya que $V_P$ contiene un número lineal de aristas no acotadas.
Es por esto que para poder referirnos al diagrama de Voronoi como una gráfica, 
agregaremos hojas $\eta_1, \ldots, \eta_{h}$ sobre cada una de las aristas no acotadas de $V_P$ suficientemente lejos, como se observa en la Figura~\ref{F_VoronoiComoArbol}.
Obtendremos así una gráfica geométrica plana sobre el conjunto de vértices de las regiones de $V_P$, a la cual denotaremos a lo largo de este trabajo por $\mathcal{V}(P)$.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=1\textwidth]{img/cap1/VoronoiComoArbol.pdf}
\caption{\small El diagrama de Voronoi visto como una gráfica $\mathcal{V}(P)$, al agregar hojas suficientemente lejos sobre cada arista no acotada.}
\label{F_VoronoiComoArbol}
\end{center}
\end{figure}

\begin{prop}\label{V(P) es un arbol}
Los vértices y aristas de $\mathcal{V}(P)$ forman una gráfica acíclica y conexa.
\end{prop}
\begin{proof}
Ya que el diagrama de Voronoi es una división del plano, 
podemos concluir que la gráfica formada por los vértices y aristas del diagrama es conexa.
Además, no puede tener ciclos puesto que ello implicaría la existencia de una región acotada.
\end{proof}

Gracias a la proposición anterior sabemos que $\mathcal{V}(P)$ es una árbol, 
sin embargo no conocemos cuál el número aristas o vértices que tiene, 
es por esto que el siguiente resultado será útil más adelante.

\begin{lma}\label{SizeVoronoi}
Si $P$ es un conjunto de $n$ puntos en el plano en posición convexa, tal que no contenga cuatro puntos cocirculares, entonces el árbol $\mathcal{V}(P)$ tiene exactamente $2n-3$ aristas.
\end{lma}
\begin{proof}
Denotaremos por $m_e,m_v,m_f$ al número de aristas, vértices y caras respectivamente que tiene el diagrama de Voronoi de $P$.
Sea $\mathcal{V'}(P)$ la gráfica obtenida de $\mathcal{V}(P)$ al contraer las $n$ hojas $\eta_1, \ldots, \eta_n$ a un sólo vértice $v_\infty$. Es claro que $\mathcal{V'}(P)$ es una gráfica plana encajable en la esfera. 

Observe que $m_f = n$, ya que el número de regiones del diagrama de Voronoi
corresponde biunívocamente con el número de puntos de $P$. 
Usamos la característica de Euler para obtener la siguiente igualdad:
\begin{equation}\label{eq:Size1}
(m_v+1) - m_e + m_f = 2.
\end{equation}

Un resultado bien conocido en Teoría de gráficas dice que $$\sum_{v\in V}\delta(v) = 2|E|.$$ 
Es decir que la suma de los grados de los vértices es igual al doble del número de aristas de la gráfica.
Cada vértice de $\mathcal{V}'(P)$ distinto de $v_\infty$ tiene grado tres, puesto que no hay cuatro puntos cocirculares, además por construcción $\delta(v_\infty) = n$, por ende: 
\begin{equation}\label{eq:Size2}
3m_v + n = \sum_{v\in\mathcal{V}'(P)}\delta(v) = 2m_e.
\end{equation}
Resolviendo el sistema de ecuaciones definido por (\ref{eq:Size1}) y (\ref{eq:Size2}) podemos concluir lo siguiente:
$$m_e = 2n-3.$$
Además, por construcción el número de aristas de $\mathcal{V}'(P)$ es igual al de $\mathcal{V}(P)$,  por lo que nuestro resultado se sigue.
\end{proof}

Note que si no podemos garantizar que no haya cuatro puntos cocirculares, entonces lo único que podemos afirmar es que $m_e \leq 2n-3$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Calculando el diagrama de Voronoi}
Sea $P$ un conjunto de $n$ puntos en el plano, en esta sección describiremos algunos métodos para calcular el diagrama de Voronoi del punto más lejano de $P$.

Note que de la Definición \ref{Definicion Region Voronoi} podemos obtener un algoritmo trivial de tiempo $O(n^2 \log n)$ para calcular a $V_P$. 
Esto puede lograrse al construir la región de Voronoi de cada punto de $P$ a partir de la intersección de $n-1$ semiplanos, sin embargo veremos que este algoritmo dista mucho de ser óptimo.
Describiremos a continuación un algoritmo aleatorio para obtener el diagrama de Voronoi del punto más lejano de $P$ en tiempo esperado $O(n\log n)$~\cite{Overmars}.

Como primer paso obtenemos el cierre convexo del conjunto $P$ en tiempo $O(n \log n)$ y consideremos los $h$ puntos de $P$ que forman parte de la frontera del cierre convexo en el orden de las manecillas del reloj. 

Dado un punto $p$ en la frontera del cierre convexo de $P$, 
definimos al punto siguiente, denotado por $cw(p)$, y al anterior de $p$, denotado por $ccw(p)$, como sus vecinos sobre el cierre convexo 
en la dirección de las manecillas del reloj y en contra de éstas respectivamente. 

Ordenamos aleatoriamente los $h$ puntos de la frontera del cierre convexo de $P$ y nos olvidamos de los puntos interiores.
Supongamos que el orden aleatorio obtenido es el siguiente: $p_1, p_2, \ldots, p_h$. 
Removemos uno por uno de estos puntos, comenzando por $p_h$ y 
continuamos en orden hasta quedarnos únicamente con los puntos $p_1, p_2$ y $p_3$. 
Justo antes de remover a $p_i$, $4\leq i \leq h$, le agregamos a este punto un apuntador a $cw(p_i)$ y otro a $ccw(p_i)$. 
Note  que una vez que un punto es removido, no puede ser el vecino anterior ni siguiente de ningún otro punto removido posteriormente.

Una vez terminado el proceso, usamos el algoritmo extraído de la definición \ref{Definicion Region Voronoi}, para calcular en tiempo constante el diagrama de Voronoi del punto más lejano de los puntos $p_1,p_2$ y $p_3$.
Calcularemos el diagrama de Voronoi incrementalmente al insertar los vértices $p_4, \ldots, p_h$ en 
ese orden. 
Supongamos que tenemos calculado el diagrama de Voronoi de los puntos $p_1,p_2, \ldots, p_{i-1}$, 
describimos a detalle el proceso de inserción del punto $p_i$ en el diagrama. 

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=1\textwidth]{img/cap1/AlgoritmoVoronoi.pdf}
\caption{\small $a)$ El proceso de inserción de $p_i$.
$b)$ El diagrama de Voronoi después de la inserción de $p_i$.}
\label{F_InsercionVoronoi}
\end{center}
\end{figure}

La región de Voronoi de $p_i$ se insertará ``entre' ' las regiones de $cw(p_i)$ y $ccw(p_i)$, de hecho, 
antes de la inserción de $p_i$, 
las regiones de Voronoi de $cw(p_i)$ y $ccw(p_i)$ son vecinas en el diagrama de los puntos $\{p_1, \ldots, p_{i-1}\}$. 
Por ende, estas regiones están separadas por una semirrecta contenida en la bisectriz de $cw(p_i)$ y $ccw(p_i)$, semirrecta a la cual supondremos que $cw(p_i)$ tiene un apuntador; ver Figura\ref{F_InsercionVoronoi}(a).
 
La bisectriz de $p_i$ y $ccw(p_i)$, denotada por $\ell$, contiene una semirrecta $\lambda $ que formará parte de la frontera de $R(p_i)$.
Note que antes de la inserción de $p_i$, $\lambda $ está contenida en la región de Voronoi de $ccw(p_i)$.
El algoritmo recorre en orden las aristas de la frontera de $R(ccw(p_i))$,
en el sentido de las manecillas del reloj, hasta encontrar aquella arista que intersecta a la recta $\ell$ en un punto $x_0$;
$\lambda $ será entonces la semirrecta con apice $x_0$ contenida en $\ell\cap R(ccw(p_i))$; ver Figura\ref{F_InsercionVoronoi}(a).

Del otro lado de la arista donde yace $x_0$, se encuentra la región de Voronoi de otro punto de $P$, digamos $p_j$, $j\in \{1, \ldots, i-1\}$.
La bisectriz de $p_j$ y $p_i$, denotada por $\ell_j$, 
definirá otra arista de la región de Voronoi de $p_i$.
Note que $x_0\in \ell_j$, puesto que $x_0$ está en la frontera tanto de $R(p_j)$ como de $R(ccw(p_i))$.
Recorremos en orden las aristas de $R(p_j)$ en el orden de las manecillas del reloj, desde $x_0$, hasta encontrar otra arista en la frontera de $R(p_j)$ que intersecte a $\ell_j$ en un punto $x_1$. 
Note que $x_1$ está en la frontera de dos regiones de Voronoi y por lo tanto, del otro lado de la arista que contiene a $x_1$, está la región de Voronoi de otro punto de $P$.

Este proceso continúa hasta encontrar una arista que intersecte la frontera de la región de Voronoi de $cw(p_i)$, momento en el cual la bisectriz de $p_i$ y $cw(p_i)$ define una nueva semirrecta, con lo cual finaliza el algoritmo; ver Figura~\ref{F_InsercionVoronoi}.
Note que el algoritmo construye la región de Voronoi de $p_i$ en el orden opuesto a las manecillas del reloj y actualiza las regiones de Voronoi visitadas durante la inserción.

\begin{tma}
Dado un conjunto $P$ de $n$ puntos en el plano, el diagrama de Voronoi del punto más lejano de $P$ se puede calcular en tiempo esperado $O(n\log n)$.
\end{tma}

\begin{proof}
Encontrar los $h$ puntos del cierre convexo de $P$ en el orden de las manecillas del reloj requiere de tiempo $O(n\log n)$. 
Sin embargo, calcular el diagrama de Voronoi del punto más lejano de estos $h$ puntos, 
se puede hacer en tiempo esperado $O(h)$. 
Para mostrar esto, nos fijamos en el momento justo después de la inserción del punto $p_i$. 
Note que si la región de Voronoi de $p_i$ consta de $k$ aristas, entonces en el proceso de inserción de $p_i$, se atravesaron exactamente $k$ regiones de Voronoi asociadas a $k$ puntos de $\{p_1, p_2, \ldots, p_{i-1}\}$; llamemos a esos puntos $p'_1, p'_2, \ldots, p'_k$.

Es fácil ver que las aristas que se atravesaron durante esta construcción, son exactamente aquellas que pertenecen al diagrama de Voronoi de $\{p'_1, p'_2, \ldots, p'_k\}$; ver Figura~\ref{F_InsercionVoronoi}(a). 
Por ende, en la inserción de $p_i$, se visitaron a lo más $2k-3$ aristas distintas, sin embargo, cada arista pudo ser visitada dos veces. 
Por consiguiente, en la construcción de la región $R(p_i)$ se visitaron a lo más $4k-6$ aristas. 
Obteniendo así una complejidad de $O(k)$ para la construcción de la región de Voronoi de $p_i$.

Note que el diagrama de Voronoi de los puntos $\{p_1, p_2, \ldots, p_{i-1}\}$ tiene exactamente $2i-3$ aristas por el Lema~\ref{SizeVoronoi}, además, cada arista estará compartida por dos regiones.
Por lo tanto, el número de aristas en promedio de cada una de las $i-1$ regiones de Voronoi de los puntos $\{p_1, p_2, \ldots, p_{i-1}\}$ es menor que cuatro.
Y ya que cada punto de $P$ tiene la misma probabilidad de ser el $i$-ésimo insertado, 
entonces podemos afirmar que el tamaño esperado de cada región de Voronoi es menor que cuatro.
Por consiguiente el tiempo esperado de la inserción del punto $p_i$ es $O(1)$ para todo $i$. 
Obteniendo así un tiempo esperado de $O(h)$ para la construcción del diagrama de Voronoi del punto más lejano.
\end{proof}

Recordemos que si tenemos los puntos en posición convexa,
 entonces nuestro algoritmo termina en tiempo lineal esperado. 
 De hecho, existe otro algoritmo que calcula el diagrama de Voronoi del punto más lejano de un conjunto de $n$ puntos en posición convexa, en tiempo $O(n)$~\cite{LinearVoronoiDiagramForConvexPolygon}.
 
Como cada arista de $\mathcal{V}(P)$ yace sobre la bisectriz de un par de puntos, supondremos de aquí en adelante que cada arista del diagrama de Voronoi tiene apuntadores a los dos puntos de $P$ que la definen.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{$P$-círculos de radio mínimo}
En esta sección analizaremos la relación que existe entre los $P$-círculos de radio mínimo y el diagrama de Voronoi del punto más lejano.
Finalmente caracterizaremos al $P$-círculo de radio mínimo y daremos un algoritmo para encontrar su centro y el valor de su radio.
Recordemos que $C_P$ denota al $P$-círculo de radio mínimo y $c_P$ a su centro. 

\begin{obs}
$C_P$ contiene al menos dos puntos de $P$ en su circunferencia.
\end{obs}

La observación anterior se puede apreciar en la Figura~\ref{F_PropiedadesC_P}(a). 
De hecho, si suponemos que no hay cuatro puntos cocirculares en $P$, entonces $C_P$ contiene a lo más tres puntos de $P$ en su circunferencia.
La observación anterior tiene trivialmente la siguiente implicación sobre la ubicación de $c_P$.

\begin{prop}\label{centro de C_P en V(P)}
El punto $c_P$ es un vértices de $\mathcal{V}(P)$ o yace en el interior de una de sus aristas.
\end{prop}
\begin{proof}
Es claro que si la circunferencia de $C_P$ pasa por dos puntos $p_1,p_2$, entonces $c_P$ se encuentra sobre la bisectriz de $p_1,p_2$ y pertenece tanto a $R(p_1)$ como a $R(p_2)$.
Por ende $c_P$ yace sobre una arista de $\mathcal{V}(P)$. 
Un argumento similar se utiliza para el caso dónde $C_P$ pasa por tres o más puntos de $P$, 
caso en el cual $c_P$ corresponde a un vértice de $\mathcal{V}(P)$; ver Figura~\ref{F_PropiedadesC_P}(b).
\end{proof}

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=1\textwidth]{img/cap1/C_P_pasa_por_V(P).pdf}
\caption{\small $a)$ Cualquier círculo que pase por un único punto de $P$, contiene otro círculo que pasa por al menos 2 puntos de $P$.
$b)$ El círculo $C_P$ pasando por tres puntos de $P$.}
\label{F_PropiedadesC_P}
\end{center}
\end{figure}

Presentamos algunas definiciones que encontraremos útiles más adelante.

\begin{defi}
Sea $x\in \mathbb{R}^2$, $C(x)$ se define como el $P$-círculo de radio mínimo con centro en $x$.
\end{defi}

Sea $x\in \mathbb{R}^2$, note que si $x$ pertenece a la región de Voronoi de un punto $p\in P$, entonces el radio de $C(x)$ está dado por la distancia entre $x$ y $p$. 
De aquí la importancia del diagrama de Voronoi del punto más lejano siempre que hablemos de $P$-círculos de radio mínimo. Veamos ahora algunas propiedades del radio de los $P$-círculos.

\begin{defi}
Sea $\rho:\mathbb{R}^2 \to \mathbb{R}$, tal que $\rho(x)$ es el  radio de $C(x)$, $x\in \mathbb{R}^2$.
\end{defi}

\begin{prop}\label{CirculosEnSegmento}
Sean $x,y$ dos puntos en el plano. Para todo $z\in [x,y]$ se cumple que $C(z)\subseteq C(x)\cup C(y)$.
Más aún, $\rho(z)\leq \max\{\rho(x), \rho(y)\}$.
\end{prop}
\begin{proof}
Sean $a$ y $b$ los dos puntos de intersección entre las circunferencias de $C(x)$ y $C(y)$. 
Para cualquier $z\in [x,y]$, defina 
$$r=d(a,z) =d(b,z)$$
y sea $C_r(z)$ el círculo de radio $r$ con centro en $z$. 
Es claro que $C_r(z)$ contiene a $C(x)\cap C(y)$ y por ende contiene también a $P$, de aquí que $\rho(z)\leq r$. 
Además es claro que $C_r(z)\subseteq C(x)\cup C(y)$ por construcción; ver Figura~\ref{F_CirculosEnSegmento}.
Por consiguiente $C(z)\subseteq C(x)\cup C(y)$.
\end{proof}

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.8\textwidth]{img/cap1/CirculosEnSegmento.pdf}
\caption{\small La prueba de la Proposición~\ref{CirculosEnSegmento}.}
\label{F_CirculosEnSegmento}
\end{center}
\end{figure}

Veremos a continuación una caracterización del punto $c_P$.
\begin{prop}\label{c_P minimo local}
El punto $c_P$ es el único mínimo local de la función $\rho$ en el plano.
\end{prop}
\begin{proof}
Supongamos que existen dos mínimos locales $x_0,x_1\in\mathbb{R}^2$ de la función $\rho$, sin pérdida de generalidad, supongamos que $\rho(x_0) \geq \rho(x_1)$.
Sea $z$ un punto en el segmento $[x_0,x_1]$ a distancia epsilon de $x_0$.
Por la Proposición~\ref{CirculosEnSegmento}, $C(z)\subseteq C(x_0)\cup C(x_1)$.
Por ende $C(z)$ es un $P$-círculo que tiene radio estrictamente menor que $C(x_0)$, 
lo cual implica que $x_0$ no es un mínimo local de $\rho$.
Contradicción que viene de suponer que existe más de un mínimo local de la función $\rho$.
\end{proof}

La proposición anterior implica trivialmente que el $P$-círculo de radio mínimo es único.

\begin{prop}\label{c no esta en el interior de [u,v]}
Sea $uv$ una arista de $\mathcal{V}(P)$ contenida en la bisectriz de los puntos $p_0,p_1\in P$.
Si  $[u,v]\cap [p_0,p_1] \neq \emptyset$, entonces $c_P = [u,v]\cap [p_0,p_1]$
\end{prop}
\begin{proof}
Sea $x\in[u,v]\cap [p_0,p_1]$.
Note que $[u,v] = R(p_0)\cap R(p_1)$, por ende $\rho(x)=d(x,p_0)=d(x,p_1)$.  
Si movemos a $x$ en cualquier dirección una epsilon distancia, entonces  $x$ se alejará de $p_0$ o de $p_1$, por lo que el radio de $C(x)$ aumentará necesariamente.
Por consiguiente $x$ es un mínimo local de la función $\rho$, lo cual usando la Proposición~\ref{c_P minimo local} implica que $x=c_P$.
\end{proof}

Analizaremos ahora el comportamiento de la función $\rho$ sobre los puntos de $\mathcal{V}(P)$.

\begin{tma}\label{monotonoia rho}
Sea $x$ un punto sobre una arista de $\mathcal{V}(P)$ y sea $T$ una trayectoria sobre el árbol $\mathcal{V}(P)$ que una al punto $c_P$ con $x$. Se cumple que $\rho$ es una función estrictamente monótona sobre los puntos de $T$ con mínimo en $c_P$.
\end{tma}
\begin{proof}
Sea $uv$ una arista de $T$ y supongamos que está contenida en la bisectriz de dos puntos $p_0,p_1\in P$.
Sean $\alpha,\beta$ dos puntos sobre el segmento $[u,v]$, 
es claro que $\rho(\alpha) = d(\alpha,p_0) = d(\alpha,p_1)$ pues $uv$ es la frontera entre las regiones $R(p_0)$ y $R(p_1)$, análogamente $\rho(\beta) = d(\beta,p_0)$.
Note que los triángulos $\Delta(p_0p_1\alpha), \Delta(p_0p_1\beta)$ son isósceles y comparten la misma base. Por ende si $\alpha$ está más lejos de la base del triángulo que $\beta$, entonces $\rho(\alpha)>\rho(\beta)$.
Por la Proposición~\ref{c no esta en el interior de [u,v]}, sabemos que $c_P$ no pertenece al interior de ninguna arista de $T$, por consiguiente $\rho$ es una función monótona sobre los puntos de la arista $uv$. 
Repitiendo el argumento recursivamente para todas las aristas de $T$ se sigue el resultado.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Calculando el $P$-círculo de radio mínimo}
Concluimos este capítulo presentando un algoritmo de tiempo $O(n)$ para encontrar al punto $c_P$ una vez calculado el diagrama de Voronoi del punto más lejano de $P$.
Existe otro algoritmo propuesto por Megiddo~\cite{LinearTimeAlgorithmsForLinearProgramming}, que encuentra al punto $c_P$ en tiempo lineal, sin la necesidad de calcular el diagrama de Voronoi.
Sin embargo, el objetivo de este capítulo es mostrar la relación que existe entre el diagrama de Voronoi y los $P$-círculos de radio mínimo.

Note que como $C_P$ pasa por  al menos dos puntos de $P$, entonces $c_P$ yace sobre la bisectriz de dos puntos de $P$.
Podríamos pensar ingenuamente, que con un algoritmo que busque a $c_P$ en cada una de las bisectrices definidas por pares de puntos de $P$ nos es suficiente.
Sin embargo el número de bisectrices a revisar es exactamente $n\choose 2$, por lo que nuestro algoritmo terminaría en al menos tiempo $O(n^2)$; veremos que podemos hacerlo mucho mejor. Pensemos a las aristas del árbol $\mathcal{V}(P)$ como segmentos cerrados, por ende, gracias a la Proposición~\ref{centro de C_P en V(P)}, $c_P$ yace sobre una arista de $\mathcal{V}(P)$.
Nuestro algoritmo revisa cada arista del árbol y determina si $c_P$ pertenece o no a esa arista como sigue. 
Sea $uv$ una arista de $\mathcal{V}(P)$ contenida en la bisectriz de $p_0,p_1$, determinamos en tiempo constante 
si $[u,v]\cap[p_0,p_1]\neq \emptyset$, en cuyo caso por la Proposición~\ref{c no esta en el interior de [u,v]}, concluimos que $c_P = [u,v]\cap[p_0,p_1]$.
El algoritmo anterior termina en tiempo lineal ya que por el Lema~\ref{SizeVoronoi}, el árbol $\mathcal{V}(P)$ tiene $O(n)$ aristas. 


 










